package leetcode.editor.cn;

//[52]N 皇后 II
public class NQueensIi52 {
    public static void main(String[] args) {
        Solution solution = new NQueensIi52().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int count = 0;

        public int totalNQueens(int n) {

            dfsbit(n, 0, 0, 0, 0);
            return count;
        }

        private void dfsbit(int n, int row, int col, int pie, int na) {
            if (row >= n) {
                count++;
                return;
            }

            //~(col | pie | na)   can input is 1,
            int bit = (~(col | pie | na) & ((1 << n) - 1));
            while (bit > 0) {

                int tail = bit & (-bit);

//                dfsbit(n, row + 1, col | tail, (pie + tail) << 1, (na + tail) >> 1);//也可以，但是 不直观。
                dfsbit(n, row + 1, col | tail, (pie | tail) << 1, (na | tail) >> 1);

                bit = bit & (bit - 1);//del tail 1
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}